package 二叉树;

import java.util.*;

public class buildTree {
    // 创建一个TreeNode类
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    // 创建一个temp数组，用于存储前序遍历的值
    static int[] temp;
    // 创建一个map，用于存储中序遍历的值和索引
    static HashMap<Integer, Integer> map = new HashMap<>();
    // 创建一个build方法，用于构建二叉树
    public static TreeNode buildTreem(int[] preorder, int[] inorder) {
        // 将前序遍历的值赋值给temp数组 
        temp = preorder;
        // 将中序遍历的值和索引存储到map中
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        // 递归构建二叉树
        return build(0, preorder.length - 1, 0, inorder.length - 1);
    }
    // 递归构建二叉树
    // 通过数组存储前序遍历的值
    // 通过map存储中序遍历的值和索引
    // 前序第一个值为根节点，通过根节点的值从map中获取中序遍历根节点的位置
    // 获取左子树的长度：index - ib 获取右子树的长度：ie - index
    // 从前序遍历中获取左子树的范围：pb + 1, pb + (index - ib)
    // 从前序遍历中获取右子树的范围：pb + (index - ib) + 1, pe
    private static TreeNode build(int pb, int pe, int ib, int ie) {
        // 如果前序遍历的开始索引大于结束索引或者中序遍历的开始索引大于结束索引，返回null
        if(pb > pe || ib > ie) return null;
        // 获取前序遍历的值
        int value = temp[pb];
        // 创建一个根节点
        TreeNode root = new TreeNode(value);
        // 获取中序遍历的值的索引
        int index = map.get(value);
        // 递归构建左子树
        root.left = build(pb + 1, pb + index - ib, ib, index - 1); 
        // 递归构建右子树
        root.right = build(pb + index - ib + 1, pe, index + 1, ie);
        // 返回根节点
        return root;
    }
    // 层序遍历
    public static List<Integer> levelOrder(TreeNode root) {
        // 创建一个res列表，用于存储层序遍历的值
        List<Integer> res = new ArrayList<>();
        // 如果根节点为空，返回空列表
        if(root == null) return res;
        // 创建一个双端队列，用于存储节点
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        // 将根节点加入队列
        deque.offer(root);
        // 当队列不为空时，继续遍历
        while(!deque.isEmpty()) {
            // 获取队列的大小
            int size = deque.size();
            // 遍历队列中的节点
            for(int i = 0; i < size; i++) {
                // 获取队列中的节点
                TreeNode cur = deque.poll();
                // 如果左子树不为空，将左子树加入队列
                if(cur.left != null) deque.offer(cur.left);
                // 如果右子树不为空，将右子树加入队列
                if(cur.right != null) deque.offer(cur.right);
                // 将节点的值加入res列表
                res.add(cur.val);
            }
        }
        // 返回res列表
        return res;
    }
    // 主函数
    public static void main(String[] args) {
        // 创建一个Scanner对象，用于读取输入
        Scanner sc = new Scanner(System.in);
        // 读取输入
        String s = sc.nextLine();
        // 将输入的字符串转换为数组
        String[] pre = s.split(",");
        // 读取输入
        String p = sc.nextLine();
        // 将输入的字符串转换为数组
        String[] in = p.split(",");
        // 将输入的数组转换为int数组
        int[] preorder = new int[pre.length];
        int[] inorder = new int[in.length];
        for(int i = 0; i < pre.length; i++) {
            preorder[i] = Integer.parseInt(pre[i]);
            inorder[i] = Integer.parseInt(in[i]);
        }   
        // 构建二叉树
        TreeNode root = buildTreem(preorder, inorder);
        // 层序遍历
        List<Integer> res = levelOrder(root);
        // 输出结果
        System.out.println(res);
        // 关闭Scanner对象
        sc.close();
    }
}
